// 分割数组_背包
// 其中dp[i]表示原数组是否可以取出若干个数字，其和为i。
// 只需要返回dp[target]就行了。初始化dp[0]为true，
// * @file     数组分割.cpp
// * @brief:   将数组分割成两部分，两部分的和相等的部分；判断是否存在这样的分割
// 思路1:递归：1、先求出这个数组的和，
// 2、看这个和能不能被2整除，可以的话再进行下一步。
// 返回一个尝试分割的函数；trypartition（numbers,index,sum/2）;
// 3、用numbers数组的[0....index]个数字来填充 sum的背包； 可以填充则返回true
// 4、tryPartition（numbers，index，sum）=tryPartition(numbers,index-1,sum)||tryPartition(numbers,index-1,sum-numbers[index])
// 思路二：动态规划：
// 1、同上并判断和能否被2整除；
// 2、并且将背包容量C=sum/2;
// 3、初始状态：demo[j];只考虑第一个元素number[0]看看能不能填充;
// 4、状态转移；for(int i=0;i<n;++i)
// for(int j=C;j>=number[i];j--)
// memo[j]=memo[j]||memo[j-number[i]]
// https://blog.csdn.net/qq_40320556/article/details/89875463
// Leetcode 题解 - 动态规划-0-1 背包（2）：划分数组为和相等的两部分
#include <assert.h>

#include <iostream>
#include <vector>
using namespace std;
bool CanPartition(vector<int>& numbers);
bool tryPartition(
    vector<int>& numbers, int index,
    int sum);  //使用numbers[0........index]来填充一个容量为sum的背包；
bool CanPartition_DP(vector<int>& numbers);
vector<vector<int>> memo;
// memo[i][c]表示使用索引[0...i]的这些元素，是否可以完全填充一个容量为C的背包，
// -1表示没有被计算，0表示不可以填充，1表示可以填充；

int main() {
  vector<int> a = {1, 5, 5, 11};
  vector<int> b = {1, 2, 3, 8};
  if (CanPartition(a))
    cout << "存在" << endl;
  else
    cout << "不存在" << endl;
  if (CanPartition_DP(b))
    cout << "存在" << endl;
  else
    cout << "不存在" << endl;
  cout << endl;
}
bool CanPartition(vector<int>& numbers) {
  int n = numbers.size();
  int sum = 0;
  for (int i = 0; i < n; i++) {
    assert(numbers[i] > 0);
    sum += numbers[i];
  }
  if (sum % 2 != 0) return false;
  memo = vector<vector<int>>(
      n, vector<int>(sum / 2 + 1,
                     -1));  //一定要多加入一列，如果不加1  会出现越界！！！
  return tryPartition(numbers, n - 1, sum / 2);
}
bool tryPartition(vector<int>& numbers, int index,
                  int sum)  //[0....index]个的number数组的数字来填充sum背包
{
  if (sum == 0) return true;
  if (sum < 0 || index < 0) return false;
  //用从0-index-1的numbers数字能不能填充这个sum的背包，能填充，所以0-index也能填充
  //只不过不使用，如果不能填充，加上index能不能填充； return
  // tryPartition(numbers, index - 1, sum) || tryPartition(numbers, index - 1,
  // sum - numbers[index]);//47行为递归用法，肯定包含重复的；
  if (memo[index][sum] != -1)
    return memo[index][sum] == 1;  //这里如果等于0，返回的是false，等于1返回true
  memo[index][sum] = (tryPartition(numbers, index - 1, sum) ||
                      tryPartition(numbers, index - 1, sum - numbers[index]))
                         ? 1
                         : 0;
  return memo[index][sum];
}
bool CanPartition_DP(vector<int>& numbers) {
  int sum = 0;
  int n = numbers.size();
  for (int i = 0; i < n; i++) {
    assert(numbers[i] > 0);
    sum += numbers[i];
  }
  if (sum % 2) return false;  //判断能不能被2整除
  int C = sum >> 1;           //背包容量
  vector<bool> memo(C + 1, false);
  for (int j = 0; j <= C;
       j++)  //容量从0-C，只考虑第一个number，看看能不能填满，
    memo[j] = (numbers[0] == j);
  for (int i = 1; i < n; i++)  //从第一个开始，放，直到最后一个
    for (int j = C; j >= numbers[i]; j--)
      memo[j] = memo[j - 1] || memo[j - numbers[i]];
  return memo[C];
}